package com.github.hgkmail.hello.interview.mysql.design;

import java.util.Map;

//自平衡的多叉叶子查找树 —— B+树
//B+树是B树的变种，节点分为内部节点和叶子节点（分别对应2个度d1和d2），内部节点只用于查找，不存放数据，数据都存放在叶子节点
//不同点1，内部节点只存放关键字和指针，不存放数据，因此可以存放很多指针，相比B树，B+树更加"矮胖"，一般最多3层（可存放2千万记录）
//不同点2，数据都在叶子节点，所以每次查询都会查到叶子节点，查询效率稳定，叶子节点通过指针链起来，遍历和区间查询十分方便，不需要中序遍历
//插入和删除与B树十分类似，但要注意一点，因为数据都在叶子节点，B+树里面有重复关键字，B树没有重复关键字。
public class BPlusTree {
    //内部节点，与B树类似
    class BPlusTreeNode {
        int[] keys; //关键字，keys[i]左边孩子是children[i]，右边孩子是children[i+1]
        BPlusTree.BPlusTreeNode[] children; //孩子节点
        int keyNum; //关键字个数
        boolean leaf; //是否叶子节点
        int degree; //最小度，一个节点关键字个数: t-1 <= keyNum <= 2t-1
    }

    //叶子节点
    class BPlusTreeLeafNode extends BPlusTreeNode {
        Object[] records; //真正的数据
        BPlusTreeLeafNode prev; //链表前指针
        BPlusTreeLeafNode next; //链表后指针
    }

    //todo

}
